/** Programme TP Ensimag 2A - AOD. Justification optimale d'un texte.
 * @author Jean-Louis.Roch@imag.fr, David.Glesser@imag.fr
 * @date 15/9/2014
 */

#include "altex-utilitaire.h"
#include <stdio.h>
#include <sys/stat.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <locale.h>
#include <limits.h>
#include <unistd.h>

/*

méthode utilisée;
les choix d’implantation suivis :
	La fonction phi(i) a été codée de manière récursive.
	Le calcul de la taille des espaces qu'il est nécessaire d'ajouter pour atteindre la longueur voulue d'une ligne comportant M mots est fait relativement au résultat pour une ligne comportant M-1 mots
	
	La taille de chaque mot est calculée :
		- une fois par la fonction read_word() dans altex() pour allouer l'espace nécessaire afin de stocker le mot en question.
		- une fois par la fonction wordlength()
		
	Nombre de fois où les données sont parcourues en mémoire :
		- le phi(i) de l'énoncé correspond à cost_para(i). Cette fonction est appelés 2^(i-1) fois donc tab_cp[i] est accédé 2^(i -1) + 1 (le +1 est dû à l'initialisation du tableau)
		- paragraph (tableau qui contient les mots de chaque paragraphe):
			- 1 accès sur chaque case pour le remplir
			- 1 accès sur chaque case pour le calcul de la longueur du mot se trouvant dans la case en question
			- 1 accès sur chaque case par drawline_word pour afficher le texte
		- tab_wl (tableau qui contient la longueur de tous les mots du paragraphe):
			- tab_wl[i] est accédé i+1 fois
		- backtrace (tableau mémorisant l'indice du premier mot de chaque ligne justifiée) :
			-backtrace[i] est accédée 2^(i -1) + 1 (le +1 est dû à l'initialisation du tableau)
*/














/** Optimal alignment of a text (read from input file in) with ligns of fixed length (M units) written on output file (out).
  * @param in: input stream, in ascii (eg in == stdin)
  * @param len: maximum number of words in the text (may be larger than the stream)
  * @param outformat: output stream, should be initialed
  * @param M: line size (in units)
  * @param N: function to optimize is #spaces^N 
  * @return: the cost of an optimal alignment
  */
long altex(FILE* in, size_t len, struct stream *outformat, unsigned long M, unsigned N) ;

/** Computes the cost of aligning a paragraph
  * @param i: index of the first word in the paragraph
  * @param paragraph: a array in which all the words of the current paragraph are stored
  * @param len_para : Index of the last word of the paragraph being treated
  * @param M: line size (in units)
  * @param N: function to optimize is #spaces^N 
  * @param outformat: output stream
  * @param tab_sta: array in which are stored the results of the function spaces_to_add(sta stands for spaces_to_add)
  * @param tab_cp: array in which are stored the results of this function (cp stands for cost_para)
  * @param void_tab: value that indicates that tab_sta[i]k] or tab_cp[i] have never been computed
  * @param backtrace: to compute tab_cp[0], tab_cp[backtrace[0]] has to be known and so on
  * @return: the cost of an optimal alignment for the paragraph
  */
long cost_para(long i, char **paragraph, size_t len_para, unsigned long M, unsigned N, struct stream *outformat, long *tab_cp, long void_tab, int *tab_wl, long *backtrace)
{
    /*if cost_para(...) has already been computed then the value is in tab_cp so no need to compute it again*/
    if (tab_cp[i] != void_tab)
        {
            return tab_cp[i];
        }
    if (i == len_para && tab_wl[i] >= 0)
    {	
    		*backtrace = i+1;
        		return 0;
    }
    else
    {
            int k = i;
            
            long sta = M - tab_wl[k];// E(i,i)
            long min = cost_para(i + 1, paragraph, len_para, M, N, outformat, tab_cp, void_tab, tab_wl, backtrace + 1) + penality(sta, N);
            k++;
			
            *backtrace = i + 1;
            sta -= sizeSeparator(outformat) + tab_wl[k];
            long cp = 0;
            while (sta >= 0)
            {
            	if (k == (long)len_para)
            	{
            		tab_cp[i] = 0;
            		*backtrace = k + 1;
          			return 0;
               	}
               	cp = cost_para(k + 1, paragraph, len_para, M, N, outformat, tab_cp, void_tab, tab_wl, backtrace + 1);
                    if (min > cp + penality(sta, N))
                    {
                        min = cp + penality(sta, N);
                        *backtrace = k + 1;
                    }
                k++;
                sta -= (sizeSeparator(outformat) + tab_wl[k]);//sta = E(i,k)
            }
            tab_cp[i] = min;
            return min;
    }
}
  
long altex(FILE* in, size_t len, struct stream *outformat, unsigned long M, unsigned N)
{
    char **paragraph = NULL; //Array of char* that will contain all the word of a paragraph
    paragraph = calloc(len, sizeof(*paragraph));
    char* buffer = (char*) calloc(len +1, sizeof(char) ) ;  // Preallocated buffer, large enough to store any word...
    long void_element = len * 2;
    int *tab_wl = calloc(len, sizeof(*tab_wl));// Contains the lengths of the words in a paragraph (wl stands for 'word length')
    size_t buffer_size = len ; 
    struct parser p_in; 
    init_parser(in, &p_in) ; 
    long maxval_all_paragraphs = 0 ;
    long sumval_all_paragraphs = 0 ;
    int endofile = 0;
    long cost = 0;
    long num_word = 0;
    long *tab_cp = NULL;//tab_cp: array in which are stored the results of cost_para(i, ...) (cp stands for cost_para)
    long *backtrace = NULL;//backtrace: to compute tab_cp[i], tab_cp[backtrace[i]] is required => used to know the first and last words of each justifies lines
    while (!endofile)
    { // We read each paragraph from the first one
        int is_paragraph_end = 0 ;
        num_word = 0;
        void_element = len * 2;
        while ( !is_paragraph_end )
        { // All words in the paragraph are stored in tabwords, character being stored in buffer..
            size_t n = read_word( &p_in, &is_paragraph_end, buffer, buffer_size ) ; // Size of the word if any
            if(n==0)
            {
                endofile = 1 ;
                break ;
            }
            if (n > N)
            {
            	word_truncate_at_length(outformat, buffer, M + 1) ;
            	n = M;
            }
           	char *word = malloc((n+1) * sizeof(*word));
            word = strncpy(word, buffer, n);
            word[n] = '\0';/*to mark the end of the string*/
            paragraph[num_word++] = word;
            tab_wl[num_word - 1] = wordlength(outformat, paragraph[num_word - 1]);// this is the only time the length of the word is computed
        }
        if(num_word > 0)
        {
            tab_cp = (long *)calloc(num_word , sizeof(*tab_cp));
            backtrace = calloc(num_word, sizeof(*backtrace));
            if (tab_cp == NULL)
            {
                if (tab_cp == NULL)
                    fprintf(stderr, "Erreur d'allocation de tab_cp");
            }
            
            /*All the elements are initialized with the value (2 * len_left) in order to know if it has been set before */
            long i;
            for(i = 0 ; i < num_word ; i++)
            {
                    tab_cp[i] = void_element;
                    backtrace[i] = void_element;
            }
            cost = cost_para(0, paragraph, num_word - 1, M, N, outformat, tab_cp, void_element, tab_wl, backtrace);

            /*Displays the word lines*/
            int word_to_cut = 0;
            int prev = 0;
            while( backtrace[word_to_cut] < (long)num_word)
            {
                prev = word_to_cut;
                word_to_cut= backtrace[word_to_cut];
                draw_wordline(outformat, word_to_cut - prev, paragraph + prev, 0 );
            }
            draw_wordline(outformat, num_word - word_to_cut, paragraph + word_to_cut, 1 );

            /*Updates sumval_all_paragraphs and maxval_all_paragraphs*/
            sumval_all_paragraphs += cost;
            if (cost > maxval_all_paragraphs)
            {
                maxval_all_paragraphs = cost;
			}


            /*freeing what has been allocated for this paragraph*/
            long h = 0;
            for( h = 0 ; h < num_word ; h++)
            {
                free(paragraph[h]);
            }
            free(tab_cp);
            free(backtrace);
        }
    }
    
    /*Freeing what is left to free*/
    free(tab_wl);
    free(paragraph);
    free(buffer) ;
    fprintf(stderr, "\n#@alignment_cost:MAX=%ld;SUM=%ld\n", maxval_all_paragraphs, sumval_all_paragraphs);
   
    return maxval_all_paragraphs;
}

//////////////////////////////////////////////////////////////////////////////


static void usage(char * prog) {
   fprintf(stderr, "usage: %s -i input_file -o output_file -f format [-m M]\n", prog);
   fprintf(stderr, "\nOptions:\n");
   fprintf(stderr, "\t-i input_file   Input file (default: stdin)\n");
   fprintf(stderr, "\t-o output_file  Output file (default: stdout)\n");
   fprintf(stderr, "\t-f format       Output format, possible formats: \n");
   fprintf(stderr, "\t                    'text' for a text file (default)\n");
   fprintf(stderr, "\t                    'serif' for a pdf file with a serif font\n");
   fprintf(stderr, "\t                    'hand' for a pdf file with a handwritten font\n");
   fprintf(stderr, "\t-m M            Where M is the width (default: 80)\n");
   fprintf(stderr, "\t                    if the format is 'text', it's the number of characters\n");
   fprintf(stderr, "\t                    else, it's in points and should be < %i points\n", (int)A4_WIDTH);
   exit(1);
}


int main(int argc, char *argv[] )
{
    //Command line parsing
    char c;
    long M = 80 ;
    char* input_file = 0;
    char* output_file = 0;
    char* format = 0;

    while ((c = getopt(argc , argv, "i:o:f:m:")) != -1)
    {
        switch (c) {
            case 'i':
                input_file = optarg;
                break;
            case 'o':
                output_file = optarg;
                break;
            case 'f':
                format = optarg;
                break;
            case 'm':
                M = atoi(optarg);
                break;
            case '?':
                usage(argv[0]);
                break;
        }
    }

    FILE* f = stdin;
    if(input_file)
    {
        f = fopen(input_file, "r") ; 
        if( f == NULL ) {
            fprintf( stderr, "Error opening input file.");
            return(-1);
        }
    }
    
    struct stat st;
    fstat(fileno(f), &st);
    size_t fsize = st.st_size;
    

    if (!setlocale(LC_CTYPE, "")) {
        fprintf( stderr, "Can't set the specified locale! "
                            "Check LANG, LC_CTYPE, LC_ALL.\n");
        return -1;
    }
    
    struct stream* outstream;
    
    if(format == 0)
        outstream = init_stream(output_file, 0, M);
    else
    {
        switch(format[0])
        {
            case 't': //"text"
                outstream = init_stream(output_file, 0, M);
                break;
            case 's': //"serif"
                outstream = init_stream(output_file, "DejaVuSerif.ttf", M);
                break;
            case 'h': //"hand"
                outstream = init_stream(output_file, "daniel.ttf", M);
                break;
            default:
                fprintf( stderr, "Unrecognized format.\n");
                    return 1;
        }
    }
    if(!outstream)
        return 1;
    altex(f, fsize, outstream, M,  2) ; 
    
    //free and flush outstream
    free_format(outstream);
    fclose( f ) ;
    return 0 ;
    }


